/* Copyright (C) 2017-2100 All right reserved
 * For free
 *
 * @file list.c
 * @brief  list 初始化以及通用接口实现
 * @author qigaohua, qigaohua168@163.com
 * @version 0.0.1
 * @date 2020-08-06
 */


#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "list.h"



static inline int list_default_node_cmp(const void *_a, const void *_b)
{
    return !(_a == _b);
}

static inline void list_default_node_free(void *val)
{
    FREE(val);
}


void list_set_free_func(list_t *l, list_node_free free)
{
    l->node_free = free;
}

void list_set_cmp_func(list_t *l, list_node_cmp cmp)
{
    l->node_cmp = cmp;
}


list_node_t *list_node_new(void *val)
{
    list_node_t *node = MALLOC(sizeof(list_node_t));
    if (!node)
        return NULL;
    node->next = NULL;
    node->prev = NULL;
    node->val  = val;
    return node;
}


void list_zero(list_t *l)
{
    BUG_ON(l == NULL);
    memset(l, '\0', sizeof(list_t));
}


list_t *list_new()
{
    list_t *newl = MALLOC(sizeof(list_t));
    if (!newl) return NULL;
    list_zero(newl);
    return newl;
}


void list_delete(list_t *l)
{
    while (l->first != NULL) {
        list_node_t *first = l->first;

        if (first->val != NULL) {
            if (l->node_free)
                l->node_free(first->val);
            else
                list_default_node_free(first->val);
        }
        l->first = first->next;
        FREE(first);
    }

    l->cnt = 0;
    l->first = l->last = NULL;
    l->node_free = NULL;
    l->node_cmp  = NULL;
}


/**
 * @brief list_insert_rignt 添加新节点到给定节点pos的右边
 *
 * @param l         list
 * @param pos       位置节点
 * @param val       添加新节点的内容
 *
 * @return          成功放回添加的节点
 */
list_node_t* list_insert_rignt(list_t *l, list_node_t *pos, void *val)
{
    list_node_t *nnode;  // new node

    BUG_ON(l == NULL);

    nnode = list_node_new(val);
    if (!nnode)
        return NULL;

    if (!pos) { // 添加到最后面
        nnode->next = NULL;
        nnode->prev = l->last;
        if (l->last) {
            l->last->next = nnode;
        }
        else
            l->first = nnode;
        l->last = nnode;
    }
    else {
        nnode->prev = pos;
        nnode->next = pos->next;
        if (pos->next)
            pos->next->prev = nnode;
        else
            l->last = nnode;
        pos->next = nnode;
    }
    l->cnt++;

    return nnode;
}



/**
 * @brief list_insert_rignt 添加新节点到给定节点pos的左边
 *
 * @param l         list
 * @param pos       位置节点
 * @param val       添加新节点的内容
 *
 * @return          成功放回添加的节点
 */
list_node_t* list_insert_left(list_t *l, list_node_t *pos, void *val)
{
    list_node_t *nnode;  // new node

    BUG_ON(l == NULL);

    nnode = list_node_new(val);
    if (!nnode)
        return NULL;

    if (!pos) { // 添加到最前面
        nnode->prev = NULL;
        nnode->next = l->first;
        if (l->first) {
            l->first->prev = nnode;
        }
        else
            l->last = nnode;
        l->first = nnode;
    }
    else {
        nnode->next = pos;
        nnode->prev = pos->prev;
        if (pos->prev)
            pos->prev->next = nnode;
        else
            l->first = nnode;
        pos->prev = nnode;

    }
    l->cnt++;

    return nnode;
}



/**
 * @brief list_rpush 从头部添加新节点
 *
 * @param l          list
 * @param val        需添加的内容
 *
 * @return           成功返回添加的节点
 */
list_node_t* list_rpush(list_t *l, void *val)
{
    return list_insert_rignt(l, l->last, val);
}


/**
 * @brief list_rpush 从尾部添加新节点
 *
 * @param l          list
 * @param val        需添加的内容
 *
 * @return           成功返回添加的节点
 */
list_node_t* list_lpush(list_t *l, void *val)
{
    return list_insert_left(l, l->first, val);
}



list_node_t * list_iterator_next(list_t *l, list_node_t **n)
{
    return *n = (*n == NULL ? l->first : (*n)->next);
}


list_node_t * list_iterator_prev(list_t *l, list_node_t **p)
{
    return *p = (*p == NULL ? l->last : (*p)->prev);
}


list_node_t * list_match_find(list_t *l, void *val,
                int(*item_cmp)(const void *, const void *))
{
    BUG_ON(l == NULL);

    list_node_t *node = NULL;
    list_node_cmp cmp = NULL;

    if (!item_cmp)
        cmp = list_default_node_cmp;
    else
        cmp = item_cmp;

    while (list_iterator_next(l, &node)) {
        if (!cmp(val, node->val)) {
            return node;
        }
    }

    return NULL;
}


list_node_t *list_find(list_t *l, void *val)
{
    return list_match_find(l, val, l->node_cmp);
}


list_node_t *list_at(list_t *l, int index)
{
    list_node_t *n = NULL;

    if (index >= 0) {
        if (index < l->cnt) {
            n = l->first;
            while(index--) list_iterator_next(l, &n);
        }
    }
    else {
        index = ~index;
        if (index < l->cnt) {
            n = l->last;
            while(index--) list_iterator_prev(l, &n);
        }
    }

    return n;
}



/**
 * @brief list_unlink 从list中删除数据节点
 *
 * @param l         list
 * @param node      node
 */
void list_unlink(list_t *l, list_node_t *node)
{
    if (node == l->first) {
        l->first = node->next;
        if (l->first)
            l->first->prev = NULL;
        else
            l->first = l->last = NULL;
    }
    else if (node == l->last) {
        l->last = node->prev;
        if (l->last)
            l->last->next = NULL;
        else
            l->first = l->last = NULL;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    l->cnt--;

    if (l->node_free)
        l->node_free(node->val);
    else
        list_default_node_free(node->val);
    FREE(node);
}


/**
 * @brief list_remove 从list中删除值为val的节点
 *
 * @param l             list
 * @param val           删除的内容
 *
 * @return              成功返回0
 */
int list_remove(list_t *l, void *val)
{
    list_node_t *rnode = NULL;

    rnode = list_find(l, val);
    if (rnode)
        list_unlink(l, rnode);
    else
        return -1;

    return 0;
}


/**
 * @brief list_lpop 从头部取出数据节点
 *
 * @param l         list
 *
 * @return
 */
list_node_t *list_lpop(list_t *l)
{
    BUG_ON(l == NULL);

    list_node_t *node = l->first;

    if (--l->cnt) {
        (l->first = node->next)->prev = NULL;
    }
    else {
        l->first = l->last = NULL;
    }

    node->next = node->prev = NULL;
    return node;
}


/**
 * @brief list_lpop 从尾部取出数据节点
 *
 * @param l         list
 *
 * @return
 */
list_node_t *list_rpop(list_t *l)
{
    BUG_ON(l == NULL);

    list_node_t *node = l->last;

    if (--l->cnt) {
        (l->last = node->prev)->next = NULL;
    }
    else {
        l->first = l->last = NULL;
    }

    node->next = node->prev = NULL;
    return node;

}



